package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 分治算法，先分再治。该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，
 * 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
 * 在debug此归并排序时，发现运行顺序为：左右根的情况。
 * 当left == right 的时候，即为分到节点大小为1时候结束掉。虽然没有return语句，但是中止掉了。
 *
 * 8w数据0.027s
 */
public class MergeSorting {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
        costTime();
    }

    public static void sort(int[] arr) {
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        mergerSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergerSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            /**
             * 分二次，合一次
             */
            mergerSort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
            mergerSort(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
            merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
        }
    }

    /**
     * @param arr 原数组，无序数组
     * @param left 第一段数组的首下标
     * @param mid  中间索引也就是=>第一段数组的尾下标
     * @param right 第二段数组的尾下标
     * @param temp  临时数组，用于中转值
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {

        // 注意在这里mid的位置是第一段数组的最后一个下标
        int i = left;  // 左序列指针
        int j = mid+1;  //右序列指针
        int t = 0;      // 临时数组下标
        //System.out.println("治理顺序为："+left+"   "+right);
        while (i<=mid && j<=right){ // 如果发现较小的值，拷贝到temp数组
            if (arr[j]<=arr[i]){
                temp[t++] = arr[j++];
            }else {
                temp[t++] = arr[i++];
            }
        }
        while (i<=mid){ //将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while (j<=right){ //将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }

        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left<=right){
            arr[left++] = temp[t++];
        }
    }
    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays3 = new int[80000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(80000);
        }
        long startTime = System.currentTimeMillis();
        sort(arrays3);
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }
}